package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/25/21 10:50 AM
 */
public class _07_判断链表是否是回文结构 {

    public static boolean isPalindrome(Node root) {

        if (root == null || root.next == null) {

            return true;
        }

        Node middleNode = findMiddle(root);

        Node preNode = null,curNode = middleNode,nextNode = null;

        while (curNode != null) {

            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }

        curNode = preNode;
        Node node = root;
        while (node.next != middleNode) {

            if (node.val != preNode.val) {

                return false;
            }
            node = node.next;
            preNode = preNode.next;
        }

        preNode = null;

        while (curNode != null) {

            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }



        return true;
    }

    public static Node findMiddle(Node root) {


        Node slow = root;
        Node fast = root;

        while (fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.next = new Node(2);
        root.next.next = new Node(2);
        root.next.next.next = new Node(1);
//        root.next.next.next.next = new Node(1);

        boolean result = isPalindrome(root);
        System.out.println(result);
    }
}
